package morris

import "fmt"

type Node struct {
	Val interface{}
	Left *Node
	Right *Node
}


/*
	摩尔斯遍历的规则

	1. 当前节点存在左节点
		找到该左节点的最右子节点，
		1）、最右子节点的右指针指向空时，修改该节点的右指针指向当前节点，当前节点来到当前节点的左节点
		1）、最右子节点的右指针指向当前节点时，修改该节点的右指针指向空，当前节点来到当前节点的右节点

	2. 当前节点不存在左节点
		当前节点来到当前节点的右指针
*/
func Morris(head *Node){
	cur := head
	fmt.Println(cur)
	for cur != nil {
		if cur.Left != nil {
			mostRight := GetMostRight(cur.Left, cur)
			if mostRight.Right == cur {
				mostRight.Right = nil
				cur = cur.Right
				fmt.Println(cur, "cur.Right")
			} else if mostRight.Right == nil {
				mostRight.Right = cur
				cur = cur.Left
				fmt.Println(cur, "cur.Left")
			}
		} else {
			cur = cur.Right
			fmt.Println(cur, "no left")
		}
	}
	fmt.Println(cur)
}

func GetMostRight(leftNode *Node, cur *Node) *Node {
	var ans *Node
	for leftNode != nil && leftNode != cur  {
		ans = leftNode
		leftNode = leftNode.Right
	}
	return ans
}